#include "LCS_Calculator.hpp"

/**
 * @brief 创建并初始化一个最长公共子序列计算器
 * @param px 第一个字符串的指针
 * @param py 第二个字符串的指针
 */
LCS_Calculator::LCS_Calculator(string *px, string *py){
    this->x = px;
    this->y = py;
    auto m = px->length();
    auto n = py->length();
    for (int i = 0; i <= m; i++)
    {
        vector<int> c_row;
        vector<char> b_row;
        for (int j = 0; j <= n; j++)
        {
            c_row.push_back(0);
            b_row.push_back(0);
        }
        this->b.push_back(b_row);
        this->c.push_back(c_row);
    }
}

/**
 * @brief 计算LCS的长度并存储LCS的查找方式
 * @note b的存放方式为一个三bit的数。第0位表示是否可以画左上箭头，第1位表示可以画左箭头，第2位表示可以画上箭头
 */
void LCS_Calculator::LCS_Length(){
    auto m = this->x->length();
    auto n = this->y->length();
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (this->x->data()[i - 1] == this->y->data()[j - 1])   //算法中字符串索引从1开始。但是实际上从0开始
            {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] |= 0x01;
                if(c[i - 1][j] == c[i][j]) b[i][j] |= 0x04;
                if(c[i][j - 1] == c[i][j]) b[i][j] |= 0x02;
            }
            else if (c[i - 1][j] > c[i][j - 1])
            {
                c[i][j] = c[i - 1][j];
                b[i][j] |= 0x04;
            }
            else if(c[i - 1][j] < c[i][j - 1]){
                c[i][j] = c[i][j - 1];
                b[i][j] |= 0x02;
            }
            else{
                c[i][j] = c[i][j - 1];
                b[i][j] |= 0x06;
            }
        }
    }
}

/**
 * @brief 从后向前递归遍历每一个可以画左上箭头的点，并将路径暂存进path
 * @param i 节点的第一个下标
 * @param j 节点的第二个下标
 * @param n 遍历的深度
 * @param path 用来存放需要打印的字符的字符数组
 */
void LCS_Calculator::Print_LCS(int i, int j, int n, char* path){
    if(n == 1){
        path[n] = this->x->data()[i-1];
        Print_Array(path, this->LCS_size);
        return;
    }
    path[n] = this->x->data()[i-1];
    for (size_t index = 0; index < this->leftup_point_deep_table[n-1].size(); index++)
    {
        if(this->leftup_point_deep_table[n-1][index][0] < i &&
                                        this->leftup_point_deep_table[n-1][index][1] < j)
            this->Print_LCS(this->leftup_point_deep_table[n-1][index][0], this->leftup_point_deep_table[n-1][index][1],
                                                n-1, path);
    }
}

/**
 * @brief 打印指定长度的字符串
 * @param path 字符串（存放的树的便利路径上要打印的内容）
 * @param len 要打印的长度
 */
void LCS_Calculator::Print_Array(char* path, int len){
    for (int i = 1; i <= this->LCS_size; i++)
    {
        cout << path[i];
    }
    this->LCS_num ++;
    cout << endl;
}

/**
 * @brief 打印所有的LCS
 */
void LCS_Calculator::Print_All_LCS(){
    char path[100];
    this->LCS_size = this->c[this->x->length()][this->y->length()];
    for (int i = 1; i <= this->x->length(); i++)
    {
        for (int j = 1; j <= this->y->length(); j++)
        {
            if (b[i][j] & 0x01)
            {
                this->leftup_point_stack.push_back({i, j});
            }
        }
    }
    this->leftup_point_deep_table.push_back({{0, 0}});
    for (size_t i = 0; i < this->LCS_size; i++)
    {
        vector<vector<int>> deep_stack;
        this->leftup_point_deep_table.push_back(deep_stack);
    }
    for (size_t i = 0; i < this->leftup_point_stack.size(); i++)
    {
        this->leftup_point_deep_table[c[this->leftup_point_stack[i][0]][this->leftup_point_stack[i][1]]].push_back({this->leftup_point_stack[i][0],
                                                                                                                this->leftup_point_stack[i][1]});                                                                                                
    }
    for (size_t i = 0; i < this->leftup_point_deep_table[this->LCS_size].size(); i++)
    {
        this->Print_LCS(this->leftup_point_deep_table[this->LCS_size][i][0],
                        this->leftup_point_deep_table[this->LCS_size][i][1],
                        this->LCS_size, path);
    }
}

/**
 * @param 运行LCS计算器
 */
void LCS_Calculator::run(){
    time_t begin, end;
    begin = clock();
    for (size_t i = 0; i < 1000000; i++)
    {
        this->LCS_Length();
    }
    //this->Print_All_LCS();
    end = clock();
    //cout << "LCS length = " << this->LCS_size << endl;
    //cout << "LCS numbers = " << this->LCS_num << endl;
    cout << "time = " << double(end - begin) / CLOCKS_PER_SEC << endl << endl;
}